home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _dfs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.1 KB  |  51 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _dfs.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  DFS  (depth first search)                                                   *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25.  
  26. list<node> DFS(const graph& G, node v, node_array<bool>& reached)
  27. { 
  28.   list<node>  L;
  29.   node_stack  S;
  30.   node w;
  31.  
  32.   if (!reached[v])
  33.    { reached[v] = true;
  34.      L.append(v);
  35.      S.push(v);
  36.     }
  37.  
  38.   while (!S.empty())
  39.    { v = S.pop(); 
  40.      forall_adj_nodes(w,v) 
  41.        if (!reached[w]) 
  42.         { reached[w] = true;
  43.           L.append(w);
  44.           S.push(w);
  45.          }
  46.     }
  47.  
  48.   return L;
  49.  
  50. } 
  51.